package sort;

import java.util.Arrays;
import java.util.Random;

// 进行排序测试
public class TestSort {
    // 测试归并排序（非递归）：
    public static void testMergeSortNo(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.mergeSortNo(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("归并排序（非递归）耗时：" + (endTime-startTime)+"ms");
    }

    // 测试归并排序：
    public static void testMergeSort(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.mergeSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("归并排序耗时：" + (endTime-startTime)+"ms");
    }

    // 测试非递归的快排（三数取中优化版）：
    public static void testQuickSortNo2(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.quickSortNo2(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("非递归快排（三数取中优化版）耗时：" + (endTime-startTime)+"ms");
    }

    // 测试非递归的快排：
    public static void testQuickSortNo(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.quickSortNo(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("非递归快排耗时：" + (endTime-startTime)+"ms");
    }

    // 测试快速排序优化（小区间直插法）：
    public static void testQuickModify2(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.quickModify2(arr,0, arr.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序优化（小区间直插法）耗时：" + (endTime-startTime)+"ms");
    }

    // 测试快速排序优化（三数取中法）：
    public static void testQuickModify(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.quickModify(arr,0, arr.length-1);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序优化（三数取中法）耗时：" + (endTime-startTime)+"ms");
    }

    // 测试快速排序（前后指针法）：
    public static void testQuickSort3(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.quickSort3(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序（前后指针法）耗时：" + (endTime-startTime)+"ms");
    }

    // 测试快速排序（挖坑法）：
    public static void testQuickSort2(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.quickSort2(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序（挖坑法）耗时：" + (endTime-startTime)+"ms");
    }

    // 测试快速排序（Hoare版）：
    public static void testQuickSort(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.quickSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("快速排序（Hoare版）耗时：" + (endTime-startTime)+"ms");
    }

    // 测试冒泡排序：
    public static void testBubbleSort(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.bubbleSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("冒泡排序耗时：" + (endTime-startTime)+"ms");
    }

    // 测试堆排序：
    public static void testHeapSort(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.heapSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("堆排序耗时：" + (endTime-startTime)+"ms");
    }

    // 测试直接选择排序：
    public static void testSelectSort(int[] arr) {
        // 如果想要保证测的是同一个数组
        arr = Arrays.copyOf(arr,arr.length);
        long startTime = System.currentTimeMillis();
        Sort.selectSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("直接排序排序耗时：" + (endTime-startTime)+"ms");
    }

    // 测试希尔排序：
    public static void testShellSort(int[] arr) {
        long startTime = System.currentTimeMillis();
        Sort.shellSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("希尔排序耗时：" + (endTime-startTime)+"ms");
    }

    // 测试插入排序
    public static void testInsertSort(int[] arr) {
        long startTime = System.currentTimeMillis();
        Sort sort = new Sort();
        sort.insertSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("直接插入排序耗时：" + (endTime-startTime)+"ms");
    }

    public static void initArray1(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i; // 有序数组
        }
    }

    public static void initArray2(int[] arr) {
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10_0000); // 随机数组
        }
    }

    // 测试时间：
    public static void main(String[] args) {
        int[] array = new int[10_0000];
        initArray1(array); // 有序数组
        //initArray2(array);  // 随机数组
        // 两个数组不能同时存在，因为对象都是针对array数组

        /*// 直接插入排序
        testInsertSort(array); // 有序数组：3ms  随机数组：831ms

        // 希尔排序
        testShellSort(array); // 有序数组：8ms  随机数组：7ms

        // 直接选择排序
        testSelectSort(array); // 有序数组：943ms  随机数组：916ms

        // 堆排序
        testHeapSort(array);  // 有序数组：15ms  随机数组：25ms
        // 在大量元素情况下，希尔排序就会稍微比堆排序快一些。但是希尔排序增量值不好寻找。

        // 冒泡排序
        testBubbleSort(array);  // 有序数组：2ms  随机数组：15260ms

        // 快速排序（Hoare版）
        testQuickSort(array);  // 有序数组：ms  随机数组：18ms
        // 测试10_0000个有序数据耗时时，会出现栈溢出！！

        // 快速排序（挖坑法）
        testQuickSort2(array);  // 有序数组：栈溢出！ms  随机数组：28ms

        // 快速排序（前后指针法）
        testQuickSort3(array);  // 有序数组：栈溢出！ms  随机数组：19ms

        // 快速排序优化（三数取中法）
        testQuickModify(array);  // 有序数组：8ms  随机数组：17ms
        // 当数据无序且数量庞大时，快排优化（三数取中法）更好，执行速度更快，效率更高

        // 快速排序优化（小区间直插法）
        testQuickModify2(array);  // 有序数组：6ms  随机数组：28ms

        // 非递归的快排
        testQuickSortNo(array);  // 有序数组：1526ms  随机数组：30ms

        // 非递归的快排（三数取中优化版）
        testQuickSortNo2(array);  // 有序数组：27ms  随机数组：37ms

        // 归并排序
        testMergeSort(array);  // 有序数组：11ms  随机数组：19ms
*/
        // 归并排序（非递归）
        testMergeSortNo(array);  // 有序数组：17ms  随机数组：20ms
    }

    // 测试排序：
    public static void main1(String[] args) {
        int[] array = {1,3,6,8,-2,5};
        Sort sort = new Sort();
        System.out.println("直接插入排序：");
        sort.insertSort(array);
        System.out.println(Arrays.toString(array));
        // 希尔排序
        System.out.println("希尔排序：");
        int[] array2 = {9,1,2,5,7,4,8,6,3,5};
        Sort.shellSort(array2); // 静态成员变量：直接类名进行调用!
        //System.out.println(array2.toString()); // 注意toString的调用方式！
        System.out.println(Arrays.toString(array2));
        // 直接选择排序
        System.out.println("直接选择排序：");
        int[] array3 = {9,1,2,5,7,4,8,6,2,5};
        //Sort.selectSort(array3); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array3));
        // 优化后直接选择排序
        System.out.println("优化直接选择排序：");
        Sort.selectSort2(array3); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array3));
        // 堆排序
        System.out.println("堆排序：");
        int[] array4 = {9,1,2,5,7,4,8,6,7,5};
        Sort.heapSort(array4); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array4));
        // 冒泡排序
        System.out.println("冒泡排序：");
        int[] array5 = {9,1,2,5,7,4,8,6,8,82};
        Sort.bubbleSort(array5); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array5));
        // 快速排序（Hoare版）
        System.out.println("快速排序（Hoare版）：");
        int[] array6 = {9,1,2,5,7,9,8,6,8,28};
        Sort.quickSort(array6); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array6));
        // 快速排序（挖坑法）
        System.out.println("快速排序（挖坑法）：");
        int[] array7 = {9,1,2,5,7,9,8,6,3,28};
        Sort.quickSort2(array7); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array7));
        // 快速排序（前后指针法）
        System.out.println("快速排序（前后指针法）：");
        int[] array8 = {9,1,2,5,7,12,8,6,3,28};
        Sort.quickSort3(array8); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array8));
        // 快速排序优化（三数取中法）
        System.out.println("快速排序优化（三数取中法）：");
        int[] array9 = {6,1,2,5,7,12,8,6,3,28};
        Sort.quickModify(array9,0,array9.length-1); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array9));
        // 快速排序优化（小区间直插法）
        System.out.println("快速排序优化（小区间直插法）：");
        int[] array10 = {6,1,2,5,7,12,8,6,9,28};
        Sort.quickModify2(array10,0,array9.length-1); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array10));
        // 非递归的快排
        System.out.println("非递归的快排：");
        int[] array11 = {12,1,2,5,7,12,8,6,9,28};
        Sort.quickSortNo(array11); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array11));
        // 非递归的快排
        System.out.println("非递归的快排（三数取中优化）：");
        int[] array12 = {12,1,2,5,7,12,8,6,9,11};
        Sort.quickSortNo2(array12); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array12));
        // 归并排序
        System.out.println("归并排序：");
        int[] array13 = {12,1,2,5,7,11,8,6,9,11};
        Sort.mergeSort(array13); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array13));
        // 归并排序
        System.out.println("归并排序（非递归）：");
        int[] array15 = {12,1,2,5,7,11};
        Sort.mergeSortNo(array15); // 静态成员变量：直接类名进行调用!
        System.out.println(Arrays.toString(array15));
    }
}
